class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.tmp = 0
        # 做递归应该先考虑递归的出口
        def depth(node):
            if not node:
                return -1
            leftdepth = depth(node.left) + 1
            rightdepth = depth(node.right) + 1
            if self.tmp < leftdepth + rightdepth:
                self.tmp = leftdepth + rightdepth
            if leftdepth > rightdepth:
                return leftdepth
            else:
                return rightdepth
        depth(root)
        return self.tmp